Search for: All records

Abstract For an integer , the Erdős–Rogers function is the maximum integer such that every ‐vertex ‐free graph has a ‐free induced subgraph with vertices. It is known that for all , as . In this paper, we show that for all , there exists a constant such thatThis improves previous bounds of order by Dudek, Retter and Rödl and answers a question of Warnke. 

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $$n \geqslant k \geqslant t \geqslant 2$$, we consider a collection of $$k$$ families $$\mathcal{A}_i: 1 \leq i \leqslant k$$ where $$\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$$ so that $$A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \varnothing$$ if and only if there are at least $$t$$ distinct indices $$i_1,i_2,\dots,i_k$$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $$\beta_{k,t}(n)$$ of the families with ground set $[n]$. 

Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result.